#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int BTTypeData;
typedef struct BinaryTreeNode
{
	BTTypeData data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;

}BTTree;

BTTree* BuyTreeNode(BTTypeData x)
{
	BTTree* node = (BTTree*)malloc(sizeof(BTTree));
	if (node == NULL)
	{
		perror("malloc fail");
		return;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTTree* CreatTree()
{
	BTTree* node1 = BuyTreeNode(1);
	BTTree* node2 = BuyTreeNode(2);
	BTTree* node3 = BuyTreeNode(3);
	BTTree* node4 = BuyTreeNode(4);
	BTTree* node5 = BuyTreeNode(5);
	BTTree* node6 = BuyTreeNode(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;

	return node1;
}

void Prevorder(BTTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;

	}
	printf("%d ", root->data);
	Prevorder(root->left);
	Prevorder(root->right);
	
}
void Inorder(BTTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Inorder(root->left);
	printf("%d ", root->data);
	Inorder(root->right);


}
void Postorder(BTTree*root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ", root->data);
}

int SizeTree(BTTree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return SizeTree(root->left) 
		+ SizeTree(root->right)
		+ 1;


}
int HeightTree(BTTree*root)
{
	if (root == NULL)
		return 0;
	int Heightleft = HeightTree(root->left);
	int Heightright = HeightTree(root->right);
	return Heightleft > Heightright 
		? Heightleft + 1 
		: Heightright + 1;
}

int Treeklevel(BTTree* root,int k)
{
	if (k == 0)
		return 0;
	if (k == 1)
		return 1;
	int lnum=Treeklevel(root->left, k - 1);
	int rnum= Treeklevel(root->right, k - 1);
	return lnum + rnum; 

}	

BTTree* TreeFind(BTTree* root, BTTypeData x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTTree* lret=TreeFind(root->left, x);
	if (lret)
		return lret;
	BTTree* rret = TreeFind(root->right, x);
	if (rret)
		return rret;

	return NULL;

}
int main()
{
	BTTree* node1=CreatTree();
	Prevorder(node1);
	printf("\n");
	Inorder(node1);
	printf("\n");
	Postorder(node1);
	printf("\n");
	int size=SizeTree(node1);
	printf("%d",size);
	printf("\n");
	int height = HeightTree(node1);
	printf("%d ", height);
	int k = Treeklevel(node1, 3);
	printf("%d ", k);
	printf("\n");
	int find = TreeFind(node1, 3);
	printf("%p ", find);
	return 0;
}